package com.fmm.easy;

public class FlowerbedQuestion {

    /**
     * @param flowerbed 0表示空 1表示有花
     * @param n 需要放入的花的数目
     * @return 是否可以放入，花和花不能相邻
     * */
    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        // 记录第一朵花的位置
        int firstIndex = -1;
        // 记录最后一朵花位置
        int lastIndex = -1;
        // 存放中间的开始位置
        int middleStart = -1;
        // 存放中间的结束位置
        int maxCount = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            int v = flowerbed[i];
            // 如果有花需要记录和计算一些东西，如果没有花直接跳过
            if (v == 1) {
                // 只要有花，就更新最后一朵花的位置
                lastIndex = i;
                // 如果是第一朵花，计算第一朵花之前最多能放几朵
                if (firstIndex == -1) {
                    firstIndex = i;
                    maxCount = i/2;
                    // 加速逻辑：只要满足了 n 就无需继续计算了
                    if (maxCount >= n) {
                        return true;
                    }
                }
                // 记录和计算花与花之间做多放多少
                if (middleStart == -1) {
                    middleStart = i;
                } else {
                    maxCount = maxCount + (i - middleStart - 2)/2;
                    middleStart = i;
                    if (maxCount >= n) {
                        return true;
                    }
                }
            }
        }
        // 如果整个花坛没有花，计算最多放多少
        if (lastIndex == -1) {
            maxCount = (flowerbed.length + 1)/2;
        } else {
            // 计算最后一朵花之后最多能放多少
            maxCount = maxCount + (flowerbed.length - 1 - lastIndex)/2;
        }
        if (maxCount >= n) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] flowerbed = {1,0,0,0,1};
        int n = 1;
        System.out.println(canPlaceFlowers(flowerbed, n));
    }
}
